import tool.Node;
import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description: 完全二叉树的节点个数
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 * 完全二叉树 的定义如下：在完全二叉树中，
 * 除了最底层节点可能没填满外，其余每层节点数都达到最大值，
 * 并且最下面一层的节点都集中在该层最左边的若干位置。
 * 若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 * @Date:Create in 21:58  2022/7/25
 */
public class countNodes0222 {

    public static void main(String[] args) {
        String s = "[1,2,3,4,5,6,null]";
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
        System.out.println(countNodes(root));
    }

    //DFS 迭代法
    public static int countNodes(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int sum = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for(int i=0;i<size;i++) {
                TreeNode node = que.poll();
                sum++;
                if(node.left!=null) que.offer(node.left);
                if(node.right!=null) que.offer(node.right);
            }
        }
        return sum;
    }

    //递归法
    public static int countNodes2(TreeNode root) {
        if(root==null) return 0;
        int left = countNodes2(root.left);
        int right = countNodes2(root.right);
        return left+right+1;
    }
}
